package cn.com.ninng;

import cn.com.ninng.common.ListNode;

/**
 * @author liulekang
 * @createdate 2021/7/28
 */
public class Problem21 {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(7,new ListNode(8,new ListNode(10)));
        ListNode l2 = new ListNode(2,new ListNode(3,new ListNode(4)));
        ListNode listNode = mergeTwoLists(l1,l2);
        System.out.println(listNode);
    }


    /**
     * 递归
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null){
                return l2;
            }
            if(l2 == null) {
                return l1;
            }
            //根本思路就是递归寻找最大的那个元素，将大的元素挂到小的元素后面
            //递归时会将小元素暂存到递归栈中
            if (l1.val > l2.val) {
                l2.next = mergeTwoLists(l2.next,l1);
                return l2;
            }else {
                l1.next = mergeTwoLists(l1.next,l2);
                return l1;
            }
    }


    /**
     * 合并+排序
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists1(ListNode l1, ListNode l2) {

        ListNode l = l1;
        //将l2挂到l1的根节点上（合并两个链表）
        while (l.next != null){
            l = l.next;
        }
        l.next = l2;
        //对合并后的链表进行排序
        l = l1;
        ListNode end = null;
        while (l.next != end){
            while (l.next != end){
                if (l.val > l.next.val){
                    int val = l.val;
                    l.val = l.next.val;
                    l.next.val = val;
                }
                l = l.next;
            }
            end = l;
            l = l1;
        }
        return l1;
    }
}
